package 排序;
/**
 * @description：快排实现
 * @author: yangyahui01
 * @date: 12/27/24 11:38 AM
 */
public class 快速排序 {
    public static void main(String[] args) {
        int[] nums = {6,3,11,9,8,2,5};
        quickSort(nums);

        print(nums);

    }

    public static void quickSort(int[] nums) {

        int length = nums.length; //数组大小

        quickSort(nums, 0, length - 1);

    }

    /**
     * @param nums  原数组
     * @param start 起始位置
     * @param end   结束位置
     */
    public static void quickSort(int[] nums, int start, int end) {

        if (start >= end) return;

        int p = partition(nums, start, end);

        quickSort(nums, start, p - 1);
        quickSort(nums, p + 1, end);
    }

    static void print(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    /**
     * 取基准值,同时比较交换元素
     *
     * @param nums
     * @param start
     * @param end
     * @return
     */
    private static int partition(int[] nums, int start, int end) {

        int pivot = nums[end]; //基准值

        int i = start;

        for (int j = start; j < end; j++) {
            if (nums[j] < pivot) {
                if (i == j) {
                    ++i;
                } else {
                    int temp = nums[i];
                    nums[i++] = nums[j];
                    nums[j] = temp;
                }
            }
        }

        int temp = nums[i];
        nums[i] = nums[end];
        nums[end] = temp;

        return i;
    }
}
